翻訳と辞書 Words near each other ・ Pa Chay Vue ・ Pa Chenar, Gilan ・ PA Child Care ・ Pa Chong ・ PA clan ・ PA Consulting Group ・ Pa Daeng ・ Pa Daeng River ・ Pa Daet ・ Pa Daet District ・ Pa Daet Subdistrict ・ Pa Daet, Chiang Mai ・ Pa Daet, Mae Suai ・ Pa Dali ・ Pa Dar ・ PA degree ・ Pa Deh ・ Pa Deh, Semnan ・ Pa Dembo Touray ・ Pa Derazan ・ Pa Di language ・ Pa Dibba ・ Pa Dillon ・ PA Ediriweera ・ Pa Emam ・ Pa Faek ・ Pa Faek, Bueng Khan ・ Pa Faek, Phayao ・ Pa Gach-e Kal Jamshid ・ Pa Gach-e Lahbari Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク PA degree ： ウィキペディア英語版 PA degree In recursion theory, a mathematical discipline, a PA degree is a Turing degree that computes a complete extension of Peano arithmetic (Jockusch 1987). These degrees are closely related to fixed-point-free (DNR) functions, and have been thoroughly investigated in recursion theory. == Background == In recursion theory, $\backslash phi\_e$ denotes the computable function with index ''e'' in some standard numbering of computable functions, and $\backslash phi^B\_e$ denotes the ''e''th computable function using a set ''B'' of natural numbers as an oracle. A set ''A'' of natural numbers is Turing reducible to a set ''B'' if there is a computable function that, given an oracle for set ''B'', computes the characteristic function χA of the set ''A''. That is, there is an ''e'' such that $\backslash chi\_A\; =\; \backslash phi^B\_e$. This relationship is denoted ''A'' ≤T ''B''; the relation ≤T is a preorder. Two sets are Turing equivalent if each is Turing reducible to the other. The notation ''A'' ≡T ''B'' indicates ''A'' and ''B'' are Turing equivalent. The relation ≡T is an equivalence relation known as Turing equivalence. A Turing degree is a collection of sets of natural numbers, such that any two sets in the collection are Turing equivalent. Equivalently, a Turing degree is an equivalence class of the relation ≡T. The Turing degrees are partially ordered by Turing reducibility. The notation a ≤T b indicates there is a set in degree b that computes a set in degree a. Equivalently, a ≤T b holds if and only if every set in b computes every set in a. A function ''f'' from the natural numbers to the natural numbers is said to be diagonally nonrecursive (DNR) if, for all ''n'', $f(n)\; \backslash not\; =\; \backslash phi\_n(n)$ (here inequality holds by definition if $\backslash phi\_n(n)$ is undefined). If the range of ''f'' is the set then ''f'' is a DNR2 function. It is known that there are DNR functions that do not compute any DNR2 function. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PA degree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.